Kontextfreie Grammatik

In der Theorie der formalen Sprachen ist eine kontextfreie Grammatik (englisch context-free grammar, CFG) eine formale Grammatik, die nur solche Ersetzungsregeln enthält, bei denen immer genau ein Nichtterminalsymbol auf eine beliebig lange Folge von Nichtterminal- und Terminalsymbolen abgeleitet wird. Die Ersetzungsregeln haben also die Form ${\displaystyle V\rightarrow w}$ (mit Nichtterminalsymbol ${\displaystyle V}$ und Zeichenkette ${\displaystyle w}$ bestehend aus Nichtterminal- und/oder Terminalsymbolen).

Weil die linke Seite einer Regel nur aus einem einzigen Nichtterminalsymbol ${\displaystyle V}$ besteht, hängt ihre Anwendbarkeit auf eine Zeichenkette nur davon ab, ob das Nichtterminalsymbol ${\displaystyle V}$ in der Zeichenkette vorkommt, nicht aber davon, in welchem Kontext es sich befindet, d. h. welche Zeichen links und/oder rechts davon stehen. Die Regeln sind also kontextfrei.

Die kontextfreien Grammatiken sind identisch mit den Typ-2-Grammatiken der Chomsky-Hierarchie.